import java.util.*;

// 哈夫曼树节点类
class HuffmanNode implements Comparable<HuffmanNode> {
    char data;
    int frequency;
    HuffmanNode left, right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
    }

    public HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) {
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }

    @Override
    public int compareTo(HuffmanNode other) {
        return this.frequency - other.frequency;
    }
}

// 链式哈夫曼树类
class LinkedHuffmanTree {
    private HuffmanNode root;
    private Map<Character, String> huffmanCodes;

    public LinkedHuffmanTree(String text) {
        buildHuffmanTree(text);
        generateHuffmanCodes();
    }

    // 构建哈夫曼树
    private void buildHuffmanTree(String text) {
        // 统计字符频率
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // 创建优先队列
        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            priorityQueue.add(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // 构建哈夫曼树
        while (priorityQueue.size() > 1) {
            HuffmanNode left = priorityQueue.poll();
            HuffmanNode right = priorityQueue.poll();
            HuffmanNode parent = new HuffmanNode(left.frequency + right.frequency, left, right);
            priorityQueue.add(parent);
        }

        root = priorityQueue.poll();
    }

    // 生成哈夫曼编码
    private void generateHuffmanCodes() {
        huffmanCodes = new HashMap<>();
        generateCodes(root, "");
    }

    private void generateCodes(HuffmanNode node, String code) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            huffmanCodes.put(node.data, code);
        }

        generateCodes(node.left, code + "0");
        generateCodes(node.right, code + "1");
    }

    // 压缩文本
    public String compress(String text) {
        StringBuilder compressedText = new StringBuilder();
        for (char c : text.toCharArray()) {
            compressedText.append(huffmanCodes.get(c));
        }
        return compressedText.toString();
    }

    // 解压缩文本
    public String decompress(String compressedText) {
        StringBuilder decompressedText = new StringBuilder();
        HuffmanNode current = root;
        for (char bit : compressedText.toCharArray()) {
            if (bit == '0') {
                current = current.left;
            } else {
                current = current.right;
            }

            if (current.left == null && current.right == null) {
                decompressedText.append(current.data);
                current = root;
            }
        }
        return decompressedText.toString();
    }
}

// 主类，用于测试
public class Main {
    public static void main(String[] args) {
        String text = "hello world";
        LinkedHuffmanTree huffmanTree = new LinkedHuffmanTree(text);

        // 压缩文本
        String compressedText = huffmanTree.compress(text);
        System.out.println("压缩文本 " + compressedText);

        // 解压缩文本
        String decompressedText = huffmanTree.decompress(compressedText);
        System.out.println("解压文本: " + decompressedText);
    }
}    